UVa/11841 - Y-game/11841.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 const int MAXN = 25;
  28
  29 bool visited[MAXN][MAXN][MAXN];
  30
  31 bool black[MAXN][MAXN][MAXN];
  32
  33 int dx[] = { -1, +0, +1, +1, +0, -1 };
  34 int dy[] = { +0, -1, -1, +0, +1, +1 };
  35 int dz[] = { +1, +1, +0, -1, -1, +0 };
  36
  37 bool inside(int x, int y, int z) {
  38     return x >= 0 and y >= 0 and z >= 0;
  39 }
  40
  41 bool blackCanWin(int sx, int sy, int sz, int n) {
  42     memset(visited, 0, sizeof visited);
  43     assert(inside(sx, sy, sz) and black[sx][sy][sz]);
  44     queue<int> q;
  45     visited[sx][sy][sz] = true;
  46     q.push(sx); q.push(sy); q.push(sz);
  47     while (q.size() > 0) {
  48         int x = q.front(); q.pop();
  49         int y = q.front(); q.pop();
  50         int z = q.front(); q.pop();
  51         //printf("popped %d, %d, %d\n", x, y, z);
  52         for (int k = 0; k < 6; ++k) {
  53             int nx = x + dx[k];
  54             int ny = y + dy[k];
  55             int nz = z + dz[k];
  56             if (!inside(nx, ny, nz)) continue;
  57             if (!black[nx][ny][nz]) continue;
  58             if (visited[nx][ny][nz]) continue;
  59             q.push(nx); q.push(ny); q.push(nz);
  60             visited[nx][ny][nz] = true;
  61         }
  62     }
  63     bool seenX = false, seenY = false, seenZ = false;
  64     for (int x = 0; x <= n; ++x) {
  65         for (int y = 0; y <= n; ++y) {
  66             for (int z = 0; z <= n; ++z) {
  67                 if (!black[x][y][z]) continue;
  68                 if (!visited[x][y][z]) continue;
  69                 seenX |= (x == 0);
  70                 seenY |= (y == 0);
  71                 seenZ |= (z == 0);
  72                 //printf("saw black cell (%d, %d, %d)\n", x, y, z);
  73             }
  74         }
  75     }
  76     //printf("seenX = %d, seenY = %d, seenZ = %d\n", seenX, seenY, seenZ);
  77     return seenX and seenY and seenZ;
  78 }
  79
  80 int main(){
  81     int n, m;
  82     while (cin >> n >> m) {
  83         if (n == 0 and m == 0) break;
  84         memset(visited, 0, sizeof visited);
  85         memset(black, 0, sizeof black);
  86
  87         for (int k = 0; k < m; ++k) {
  88             int x, y, z;
  89             cin >> x >> y >> z;
  90             black[x][y][z] = true;
  91         }
  92
  93         bool blackWins = false;
  94         for (int x = 0; x <= n; ++x) {
  95             for (int y = 0; y <= n; ++y) {
  96                 for (int z = 0; z <= n; ++z) {
  97                     if (!black[x][y][z]) continue;
  98                     if (visited[x][y][z]) continue;
  99                     if (x != 0 and y != 0 and z != 0) continue;
 100
 101                     assert(black[x][y][z]);
 102                     blackWins |= blackCanWin(x, y, z, n);
 103                     if (blackWins) {
 104                         x = y = z = n; // ultra break
 105                     }
 106                 }
 107             }
 108         }
 109         printf("%s\n", blackWins ? "Benny" : "Willy");
 110     }
 111     return 0;
 112 }